package myself.a013Map;


import java.util.*;

/**
 * @author 叶之越
 * Description
 * Date 2021/2/1
 * Time 14:58
 * Mail 739153436@qq.com
 */
public class TopologicalOrderBFS {

    // ======================= 自己熟悉的图的数据结构 ============================
    // 拓扑排序
    public static List<Node> sortedTopology(Graph graph) {

        Map<Node, Integer> map = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        // 遍历找入度为0的节点
        for (Node value : graph.nodes.values()) {
            map.put(value, value.in);
            if (value.in == 0) {
                queue.add(value);
            }
        }
        // 队列进行遍历和更新直到队列为空
        List<Node> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            result.add(cur);
            for (Node next : cur.nexts) {
                map.put(next, map.get(next) - 1);
                if (map.get(next) == 0) {
                    queue.add(next);
                }
            }
        }
        return result;
    }


    // ======================= 其他题目提供的数据结构 ============================
    public static class DirectedGraphNode {
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;

        public DirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }
    }

    // 入度实现
    public static List<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        // 放入Map
        Map<DirectedGraphNode, Integer> map = new HashMap<>();
        for (DirectedGraphNode directedGraphNode : graph) {
            map.put(directedGraphNode, 0);
        }
        // 计算入度
        for (DirectedGraphNode directedGraphNode : graph) {
            for (DirectedGraphNode neighbor : directedGraphNode.neighbors) {
                map.put(neighbor, map.get(neighbor) + 1);
            }
        }
        // 入队
        Queue<DirectedGraphNode> queue = new LinkedList<>();
        for (Map.Entry<DirectedGraphNode, Integer> entry : map.entrySet()) {
            if (entry.getValue().equals(0)) {
                queue.add(entry.getKey());
            }
        }
        // 结果集生成
        List<DirectedGraphNode> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            DirectedGraphNode cur = queue.poll();
            result.add(cur);
            for (DirectedGraphNode neighbor : cur.neighbors) {
                map.put(neighbor, map.get(neighbor) - 1);
                if (map.get(neighbor).equals(0)) {
                    queue.add(neighbor);
                }
            }
        }
        return result;
    }

    // 通过深度大小来实现
    public static List<DirectedGraphNode> topSort2(ArrayList<DirectedGraphNode> graph) {
        if (graph == null) {
            return new ArrayList<>();
        }
        Map<DirectedGraphNode, Record> map = new HashMap<>();
        for (DirectedGraphNode node : graph) {
            deep(node, map);
        }
        List<Record> sort = new ArrayList<>();
        for (Record value : map.values()) {
            sort.add(value);
        }
        Collections.sort(sort, (o1, o2) -> o2.deep - o1.deep);
        List<DirectedGraphNode> result = new ArrayList<>();
        for (int i = 0; i < sort.size(); i++) {
            result.add(sort.get(i).node);
        }
        return result;
    }

    private static Record deep(DirectedGraphNode node, Map<DirectedGraphNode, Record> map) {

        if (map.containsKey(node)) {
            return map.get(node);
        }
        int deep = 0;

        if (node.neighbors != null || node.neighbors.size() != 0) {
            for (DirectedGraphNode neighbor : node.neighbors) {
                deep = Math.max(deep, deep(neighbor, map).deep);
            }
        }
        Record ans = new Record(node, deep + 1);
        map.put(node, ans);
        return ans;
    }


    public static class Record {
        public DirectedGraphNode node;
        public int deep;

        public Record(DirectedGraphNode n, int o) {
            node = n;
            deep = o;
        }
    }
}
